package com.squirrel.michale;

import java.util.Scanner;

/**
 *
 *
 *
 *
 *
 * Permutation Sequence
 * The set [1, 2, 3, ..., n] contains a total of n! unique permutations.
 *
 * By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
 *
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * Given n and k, return the kth permutation sequence.
 *
 * Example 1:
 *
 * Input: n = 3, k = 3
 * Output: "213"
 * Example 2:
 *
 * Input: n = 4, k = 9
 * Output: "2314"
 * Example 3:
 *
 * Input: n = 3, k = 1
 * Output: "123"
 *  
 *
 * Constraints:
 *
 * 1 <= n <= 9
 * 1 <= k <= n!
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutation-sequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * permutation (n.)
 * late 14c., permutacioun, "interchange, concurrent change; exchange of one thing, position, condition, etc., for another," from Old French permutacion "change, shift" (14c.), from Latin permutationem (nominative permutatio) "a change, alteration, revolution," noun of action from past participle stem of permutare "change thoroughly, exchange," from per "thoroughly" (see per) + mutare "to change" (from PIE root *mei- (1) "to change, go, move"). The sense of "a linear arrangement of objects resulting from a change of their order" is by 1710, originally in mathematics.
 */


public class LeetCode0060 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String combationOfIndex = "";

        while (sc.hasNextInt()) {// 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
          int   a = sc.nextInt();
          int   b = sc.nextInt();

            combationOfIndex = getCombationOfIndex(a,b);
            System.out.println(combationOfIndex);
        }

    }

    public static String getCombationOfIndex(int n,int index){
        boolean[] used = new boolean[n];
        int allCombationCount = 1;

        for(int i = 1;i<n;i++){
            allCombationCount *= i;
        }

        StringBuffer sb = new StringBuffer("");


        caculate(n,allCombationCount,index,used,sb);

        return sb.toString();

    }

    public  static void  caculate(int n,int allCount,int index,boolean[] used,StringBuffer sb){

        int swiftNext = index%allCount;

        int group = index/allCount+(swiftNext==0?0:1);
        if(swiftNext == 0){
            swiftNext = allCount;
        }

        int i = 0;

        for(;i<used.length && group >0;i++){
            if(!used[i]){
                group--;
            }
        }

        used[i-1] = true;
        sb.append(i);
        if(n == 1){
            return;
        }else{
            caculate(n-1,allCount/(n-1),swiftNext,used,sb);
        }



    }
}
